package algorithm.array;

import java.util.HashSet;
import java.util.Set;

/**
 * https://leetcode-cn.com/problems/longest-consecutive-sequence/
 * Hard
 *
 * 最长连续数列
 *
 * Created by yzy on 2021-03-04 16:31
 */
public class LongestConsecutive {
    public static void main(String[] args) {
        int[] arr = new int[]{100,4,200,1,3,2};
        System.out.println(longestConsecutive(arr));
    }

    /**
     * 时间复杂度O(N)
     * 第一遍用Hash全部把数字存起来
     * 第二遍，用数字找最长连续数列，用过的数记下来不要在用，在第二遍可以跳过很多
     * @param nums
     * @return
     */
    public static int longestConsecutive(int[] nums) {
        int max = 0;
        Set<Integer> numsSet = new HashSet<>();
        for(int num : nums){
            numsSet.add(num);
        }

        Set<Integer> usedNumSet = new HashSet<>();
        for(int num : nums){
            if(usedNumSet.contains(num)){
                continue;
            }

            int len = 1;
            usedNumSet.add(num);

            int tmpPre = num-1;
            while(numsSet.contains(tmpPre) && !usedNumSet.contains(tmpPre)){
                usedNumSet.add(tmpPre);
                tmpPre--;
                len++;

            }
            int tmpAfter = num+1;
            while(numsSet.contains(tmpAfter) && !usedNumSet.contains(tmpAfter)){
                usedNumSet.add(tmpAfter);
                tmpAfter++;
                len++;
            }
            max = max > len ? max : len;
        }

        return max;
    }
}
